package main.动态规划;

/**
 * @author tmh
 * @date 2024/9/4 20:40
 * @description
 */
public class T416分割等和子集 {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        int len = nums.length;
        for (int num : nums) {
            sum += num;
        }
        //把nums分为两个子数组，那么说明nums里面的元素之和一定是偶数
        if (sum % 2 == 1) {
            return false;
        }
        //构造一个二维数组
//        状态定义：dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于 j。
//        状态转移方程：很多时候，状态转移方程思考的角度是「分类讨论」，对于「0-1 背包问题」而言就是「当前考虑到的数字选与不选」。
//        不选择 nums[i]，如果在 [0, i - 1] 这个子区间内已经有一部分元素，使得它们的和为 j ，那么 dp[i][j] = true；
//        选择 nums[i]，如果在 [0, i - 1] 这个子区间内就得找到一部分元素，使得它们的和为 j - nums[i]。
//        状态转移方程：
//
//        dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
//
//        作者：liweiwei1419
//        链接：https://leetcode.cn/problems/partition-equal-subset-sum/solutions/13059/0-1-bei-bao-wen-ti-xiang-jie-zhen-dui-ben-ti-de-yo/
//        来源：力扣（LeetCode）
//        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\
        int target = sum / 2;
        //要算容量为0的情况，所以这里是target+1
        boolean[][] dp = new boolean[len][target+1];
        //先填一下表格的第0行
        if (nums[0] <= target) {
            dp[0][nums[0]] = true;
        }
        //开始填表格
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j <= target; j++) {
                //先把上面一行的数据抄下来
                dp[i][j] = dp[i - 1][j];

                if (nums[i] == j) {
                    dp[i][j] = true;
                    continue;
                }
//        不选择 nums[i]，如果在 [0, i - 1] 这个子区间内已经有一部分元素，使得它们的和为 j ，那么 dp[i][j] = true；
//        选择 nums[i]，如果在 [0, i - 1] 这个子区间内就得找到一部分元素，使得它们的和为 j - nums[i]。
                if (nums[i] < j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[len - 1][target];
    }
}
